Most computer architectures and their corresponding instruction sets perform binary operations called bitwise operations. Bitwise operations are statements that contain two operands joined by a bitwise operator. The operation result is a numeric value, usually in binary form. For example, the 64-bit Intel Architecture (IA-64) has four operations: AND (A&B), OR (A|B), XOR (A^B), and ANDCM (A & (˜B)). The 32-bit Intel Architecture (IA-32) has only three operations: AND, OR, and XOR (although the Streaming Single Instruction Multiple Data (SIMD) Extensions 3 (SSE3) instruction set includes all four operations). Bitwise expressions are statements that represent bitwise operations. In general, optimization of an arbitrary bitwise expression is Non-deterministic Polynomial-time (NP) hard.
The name “compiler” is primarily used for programs that translate a program written in a high level language, typically referred to as source code, into an executable program represented in a lower level language (e.g., assembly language or machine language), typically referred to as object code. Compiler optimization is the process of tuning the output of a compiler to minimize some attribute (or maximize the efficiency) of the object code. The most common requirement in compiler optimizations is to minimize the time taken to execute the object code. One way to minimize the time taken to execute a program is to minimize the number of instructions needed to compute the value of an expression. In traditional compiler science, circuit design associated with compilers and optimizations does not distinguish between expressions having large numbers of variables (e.g., more than 5) and expressions having a small number of variables. Computer programmers frequently employ a single hard-coded pattern for optimizing instructions associated with expressions having both large and small numbers of variables. This universal approach allows a compiler to affect a wide range of expressions, but does not necessarily minimize the complexity and/or the latency of the code associated with a particular expression, including an expression having a small number of variables.